Product Code Database
Example Keywords: pajamas -scarf $37-169
barcode-scavenger
   » » Wiki: Concave Game
Tag Wiki 'Concave Game'.
Tag

In , a concave game is a generalization of the defined by Rosen. He extended the theorem on existence of a , which originally proved for normal-form games, to concave games.


From normal-form games to concave games
We will describe the generalization step by step.

1. In a normal-form game, each player i can choose one of mi pure actions. The set of strategies available to each player is the set of lotteries over the pure actions, which is a in R mi.

  • In a concave game, the set of strategies available to each player may be any in R mi.

2. In a normal-form game, the set of strategies available to each player is independent of the strategies chosen by other players. This means that the set of all possible strategy profiles (denoted S) is a Cartesian product of the sets of strategies available to the players (in other words, the constraints on each player's choices are orthogonal).

  • In a concave game, the set of strategy profiles may be any in R m (where m:= m1+...+ mn). This means that the constraints on each player's choice are coupled - each player's available strategies may depend on what other players choose (such "coupled constraints" were also studied earlier by Debreu).

3. In a normal-form game, the utility function of each player i (denoted ui - a real-valued function on S) is a in each of its components, for any fixed value of the other components (for each agent j, given any choice of strategies by the other agents, the payoff of agent i is a linear function in the probabilities by which agent j chooses his pure actions).

  • In a concave game, each ui can be any continuous function that is in the strategy of agent i.
  • To state this property more explicitly, fix some strategies for all players except i; denote them by x1,...,xi-1,xi+1,...,xn, or using the shorthand notation x-i. Fix some two possible strategies for player i; denote them by xi, yi, such that both ( xi, x-i) and ( yi,x-i) are in S. Choose some value t in 0,1. Note that, since S is convex, every convex combination of xi, yi is in S too; particularly, (1- t)* xi+ t* yi is in S. The concavity requirement is that ui(1- t)* xi+ t* yi ≥ (1- t)* ui( xi) + t* ui( yi).


Existence of equilibrium
If the above conditions hold (that is, the space S of possible strategy profiles is convex, and each payoff function ui is continuous in all strategies and of all players concave in the strategy of player i), then an equilibrium exists. The proof uses the Kakutani fixed-point theorem.


Uniqueness of equilibrium
Rosen also proved that, under certain technical conditions which include strict concavity, the equilibrium is unique. The conditions are explained below.

Assume that the space S of allowed strategy profiles is defined by some k functions (representing constraints), that is, S = \{x\in \mathbb{R}^m | h_1(x)\geq 0 , \ldots, h_k(x)\geq 0 \}. In a normal-form game, the constraint functions are linear functions defining the simpices of the players; in a concave game, the hj can be any of x. For the uniqueness proof, it is also required that each hj has continuous first derivatives at any x in S.

Assume also that, for each player i, the utility function ui has continuous first derivatives at the components of xi (that is, each player's utility is continuously differentiable in the player's own strategy).

For any fixed positive vector r>0 in R n, define the r-weighted-sum of the players' payoffs:

f(x,r) := r\cdot u(x) = \sum_{i=1}^n r_i \cdot u_i(x).

Define the pseudogradient of f:

g(x,r) := r_1\cdot

where \bigtriangledown_i u_i(x) is the of ui with respect to the xi components. So \bigtriangledown_i u_i(x) is a vector in R mi and g(x,r) is a vector in R m.

We say that f is diagonally-strictly-concave at r if for every x,y in S: (y-x)\cdot g(x,r) + (x-y)\cdot g(y,r) > 0

  • For orthogonal constraint sets, if there exists some r>0 for which f is diagonally-strictly-concave at r, then the concave game has a unique equilibrium.
  • For coupled constraint sets, if there exists a convex subset Q of R m such that, for every r in Q, f is diagonally-strictly-concave at r, then for each r in Q, the game has a unique r-normalized equilibrium (an equilibrium where the Lagrange multipliers have the same proportion as r).

A sufficient condition for f being diagonally-strictly-concave at r is that the G( x, r)+ GT( x, r) is negative definite. See the paper for an example for .


Convergence to equilibrium
Consider a dynamic model of a concave game in which each player changes his strategy such that the strategy-profile remains in S, and subject to that, his utility increases. Each player i changes his strategy at rate ri in the direction of the gradient defining the maximum utility increase subject to the constraints. This results in a set of n differential equations. For any concave game and any staring point in S, this set of differential equations has a continuous solution x(t) that remains in S for all t>0.

If, in addition, the matri x G( x, r)+ GT( x, r) is negative definite for all x in S, then the solution x( t) converges to an equilibrium point as t approaches infinity.

If, in addition, the matri x G( x, r)+ GT( x, r) is negative definite for all x in S, then the solution x( t) converges to the unique r-normalized equilibrium point.


Correlated equilibrium
Takashi Ui shows that the same condition that guarantees uniqueness of a Nash equilibrium also guarantees uniqueness of a Correlated equilibrium. Moreover, an even weaker condition guarantees the uniqueness of a correlated equilibrium - a generalization of a condition proved by .


Computation of equilibrium
Based on the above results, it is possible to compute equilibrium points for concave games using for convex optimization.


Theory
Papadimitriou, Vlatakis-Gkaragkounis and Zampetakis prove that computing an equilibrium in a concave game is . In fact, they prove that the problem is in PPAD even for general concave games, and it is PPAD-hard even in the special case of strongly-concave utilities that can be expressed as multivariate polynomials of a constant degree with axis-aligned box constraints.

Filos-Ratsikas, Hansen, Hogh and Hollender


Practice
Arrow and Hurwicz presented s for solving two-player s with non-linear utilities.

Krawczyk and Uryasev studied infinite games with nonlinear utilities and coupled constraints. Starting from an existing Relaxation method, they improved it by adding steepest-descent step-size control and other improvements, and proved that it indeed converges to an equiilbrium. They tested their algorithm numerically on several applications, such as pollution of a , and showed that it converges quickly on a wide range of parameters.

Krawczyk explains numerical methods converging to an equilibrium, focusing on the case of coupled constraints. He presents several application examples using a suite called NIRA.

Chernov presents two numerical search approaches for computing equilibrium points, that have guaranteed convergence without additional requirements on the objective functions: (1) using the method for residual function minimization (2) an intermediate between the relaxation algorithm and the Hooke-Jeeves method of configurations. Convergence is proved for one-dimensional sets of players strategies. The approaches are tested using numerical experiments.


Variants
Flam and Ruzcynzki define a convex-concave game. This is a game in which the space S of strategy profiles is convex, as in Rosen's definition. But instead of requiring smoothness and other conditions on g( x, r), they allow non-smooth data, and only require that the following function is convex in x and concave in y: L(r,x,y) := \sum_{i=1}^n r_i\cdot u_i(x) - u_i(y_i, x_{-i}).

For such convex-concave games, they present two algorithms for finding equilibria, both using partial regularizations and relaxed subgradient projections. They prove that these algorithms converge.


See also
  • Nash equilibrium computation
  • Best response dynamics
  • Saddle-point method - a method for finding max-min points.

Page 1 of 1
1
Page 1 of 1
1

Account

Social:
Pages:  ..   .. 
Items:  .. 

Navigation

General: Atom Feed Atom Feed  .. 
Help:  ..   .. 
Category:  ..   .. 
Media:  ..   .. 
Posts:  ..   ..   .. 

Statistics

Page:  .. 
Summary:  .. 
1 Tags
10/10 Page Rank
5 Page Refs